package question.solution403;

import question.SolutionTemplate;

import java.util.List;

public class Solution403 implements SolutionTemplate {

    public boolean canCross(int[] stones) {
        if(stones[1] - stones[0] != 1){
            return false;
        }
        return goNext(stones, 1, 1);
    }

    private boolean goNext(int[] stones, int currentIndex, int lastStep){
        if(currentIndex == stones.length-1){
            return true;
        }
        if(currentIndex > stones.length-1){
            return false;
        }
        int[] possibleNextSteps = getKstepIndex(stones, currentIndex ,lastStep);

        return (possibleNextSteps[0] == 0 ? false : goNext(stones, possibleNextSteps[0],lastStep-1))
                || (possibleNextSteps[1] == 0 ? false : goNext(stones, possibleNextSteps[1],lastStep))
                || (possibleNextSteps[2] == 0 ? false : goNext(stones, possibleNextSteps[2],lastStep+1));
    }

    private int[] getKstepIndex(int[] stones, int currentIndex, int k){
        int[] result = new int[3];
        for (int j=currentIndex+1;  j < currentIndex + k + 1 && j < stones.length; j++) {
            if(stones[j] == stones[currentIndex] + k - 1){
                result[0] = j;
            }
            if(stones[j] == stones[currentIndex] + k){
                result[1] = j;
            }
            if(stones[j] == stones[currentIndex] + k + 1){
                result[2] = j;
            }
        }
        if(result[0] != 0){
            if(result[0] <=stones.length-3){
                if(stones[result[0]+1] == stones[currentIndex] + k){
                    result[1] = result[0] + 1;
                    if(stones[result[0]+2] == stones[currentIndex] + k + 1){
                        result[2] = result[0] + 2;
                    }
                }else if(stones[result[0]+1] == stones[currentIndex] + k + 1){
                    result[2] = result[0] + 1;
                }
            }else if(result[0] <=stones.length-2){
                if(stones[result[0]+1] == stones[currentIndex] + k){
                    result[1] = result[0] + 1;
                }else if(stones[result[0]+1] == stones[currentIndex] + k + 1){
                    result[2] = result[0] + 1;
                }
            }
        }else if(result[1] != 0){
            if(result[1] <=stones.length-2){
                if(stones[result[1]+1] == stones[currentIndex] + k + 1){
                    result[2] = result[1] + 1;
                }
            }
        }
        return result;
    }

//    public boolean canCross2(int[] stones) {
//        if(stones[1] - stones[0] != 1){
//            return false;
//        }
//        int size = stones.length;
//        boolean[][] dp = new boolean[size][size];
//        for (int i = 0; i < ; i++) {
//
//        }
//        return goNext(stones, 1, 1);
//    }

    @Override
    public void test() {
        int[] stones = {0,1,2,3,4,8,9,11};
        boolean result = canCross(stones);
        System.out.println();
    }

}
